#pragma once
#include <iostream>
#include <ctime>
#include<vector>
#include<algorithm>

const int num_vari = 4;
const int len = 20;
const int size = 50;
typedef struct node 
{	//染色体结构体
	bool chromo[num_vari][len];
}node;

template <class T>
class MyGA {
public:
	MyGA(int n_generation, int Size, int num_vari, int len, double pcross,double pmutate,double lower[],double upper[],double (*f)(T []) )
	{
		_n_generation = n_generation;
		_Size = Size;
		_num_vari = num_vari;
		_len = len;
		_pcross = pcross;
		_pmutate = pmutate;
		_lower = lower;
		_upper = upper;
		_f = f;
		bestchromo = NULL;
		group = new node[3*Size];
		temp = new node[3*Size];
	}
	template<int n>
	void GA(T (&x)[n], double& number);
private:
	int _n_generation;//进化代数
	int _Size;//种群规模
	int _num_vari;//每条染色体包含变量的个数
	int _len;//每个变量的长度,越长,GA搜索得到的值精度越高
	double _pcross;//交叉概率
	double _pmutate;//变异概率
	double* _lower;//解区间下界
	double* _upper;//解区间上界
	double (*_f)(T []);
	double _bestval;//适应值最大值
	node* bestchromo;//记录最优个体
	node* group;//记录种群中的个体的数组
	node* temp;//记录种群中的个体的临时数组
	void create();
	template<int n>
	void decode(node& c, T (&x)[n]);
	double fitness(node& c);
	void cross(node& c1, node& c2, int point);
	void mutate(node& c);
	void select();
	template<int n>
	int getBest(T (&x)[n], double& number);
	double inline rand0() 
	{	//产生0到1的随机小数
		return rand() % 10000 / 10000.0;
	}
};

//MyGA.cpp
using namespace std;
template <class T>
void MyGA<T>::create()
{	//对单个染色体上的各个变量随机赋值
	srand((unsigned)time(NULL));//产生随机数种子
	for(int k =0; k < _Size; k++)
	{
		for(int i =0; i < _num_vari; i++)
		{
			for (int j = 0; j < _len; j++) 
			{
				group[k].chromo[i][j] = rand() % 2;
			}
		}
	}
}

template <class T>
template<int n>
void MyGA<T>::decode(node& c, T (&x1)[n]) 
{	//二进制解码操作
	int num = pow((double)2, _len);//即2的10次方
	for(int i = 0; i < _num_vari; i++ )
	{
		double tem = 0;
		int m = 1;
		for (int j = 0; j < _len; j++) 
		{
			tem += c.chromo[i][j] * m;
			m *= 2;
		}
		//解码后的数据(一条染色体)放在x中
		x1[i] = (_upper[i]-_lower[i])*(tem / num)+_lower[i];
	}
}

template <class T>
double MyGA<T>::fitness(node& c) 
{	//适应度函数
	T x1[num_vari];
	decode(c, x1);
	return _f(x1);
}

template <class T>
void MyGA<T>::cross(node& c1, node& c2, int point) 
{
	for(int i =0; i < _num_vari; i++)
	{
		for (int j = 0; j < _len; j++) 
		{
			group[_Size].chromo[i][j] = c1.chromo[i][j];
			group[_Size + 1].chromo[i][j] = c2.chromo[i][j];
		}
	}
	_Size += 2;
	//交叉操作
	node c3 = c1;
	for(int k=0; k < _num_vari; k++)
	{
		for (int i = 0; i < len - point; i++) 
		{
			c1.chromo[k][point + i] = c2.chromo[k][point + i];
		}
		for (int j = 0; j < len - point; j++) 
		{
			c2.chromo[k][point + j] = c3.chromo[k][point + j];
		}
	}
}

template <class T>
void MyGA<T>::mutate(node& c) 
{	//变异操作
	for(int j = 0; j < _num_vari; j++)
	{
		int i = rand() % len;
		c.chromo[j][i] = !c.chromo[j][i];
	}
}

template <class T>
void MyGA<T>::select() 
{	//选择操作
	//double* fitnessval = new double[_Size];
	int n = _Size;
	double* fitnessval= new double[_Size];
	double sum = 0;
	double* avgfitness= new double[_Size];
	int* id = new int[_Size];

	for (int i = 0; i < _Size; i++) 
	{
		fitnessval[i] = fitness( group[i] );
	}

	//这里可以适当地排个序
	vector<int> idx( _Size);
	for (int i = 0; i != idx.size(); ++i) idx[i] = i;
	// 根据fitnessval的值对索引排序
	sort(idx.begin(), idx.end(), [&](const int& a, const int& b) {return (fitnessval[a] < fitnessval[b]);});//没有问题
	int j = 0;
	int k = 0;
	if(_Size != size)
	{
		node* group0 = new node[_Size];
		double* fitnessval0 = new double[_Size];
		for (int i = _Size - size; i < _Size; i++) 
		{
			group0[j] = group[idx[i]];
			fitnessval0[k] = fitnessval[idx[i]];
			sum += fitnessval0[k];//适应度总和
			j++;
			k++;
		}
		_Size = size;
		for (int i = 0; i < _Size; i++)
		{
			fitnessval[i] = fitnessval0[i];
			group[i] = group0[i];
		}
        delete group0;
		delete fitnessval0;
	}
	else
	{
		node* group1 = new node[_Size];
		double* fitnessval1 = new double[_Size];
		for (int i = 0; i < _Size; i++) 
		{
			group1[i] = group[idx[i]];
			fitnessval1[i] = fitnessval[idx[i]];
			sum += fitnessval[i];//适应度总和
		}
		for (int i = 0; i < _Size; i++)
		{
			fitnessval[i] = fitnessval1[i];
			group[i] = group1[i];
		}
        delete group1;
		delete fitnessval1;
	}

	for (int i = 0; i < _Size; i++) 
	{
		avgfitness[i] = fitnessval[i] / sum;
	}
	for (int i = 1; i < _Size; i++) 
	{	//适应度累加
		avgfitness[i] += avgfitness[i - 1];
	}
	//生成的新个体数目等同于_Size
	for (int i = 0; i < _Size; i++) 
	{	//轮盘赌选择法
		double rannum = rand0();//产生0到1随机数
		int j;
		for (j = 0; j < _Size - 1; j++) 
		{
			if (rannum < avgfitness[j]) 
			{
				id[i] = j;
				break;
			}
		}
		if (j == _Size - 1) 
		{
			id[i] = j;
		}
	}
	for (int i = 0; i < _Size; i++) 
	{	//将新个体替换旧个体
		temp[i] = group[i];
	}
	for (int i = 0; i < _Size; i++) 
	{
		group[i] = temp[id[i]];
	}
    delete fitnessval;
	delete avgfitness;
	delete id;
}

template <class T>
template<int n>
int MyGA<T>::getBest(T (&x)[n], double& number) 
{	//取得最优个体对应的位置
	double* fitnessval=new double[_Size];
	double a;
	for (int i = 0; i < _Size; i++) 
	{
		fitnessval[i] = fitness(group[i]);
	}
	int max_id = 0;
	for (int i = 1; i < _Size; i++) 
	{
		if (fitnessval[i] > fitnessval[max_id]) 
		{
			max_id = i;
		}
	}
	//当前最值对应的x,以及最值number
	decode(group[max_id], x);
	number = _f(x);
    delete fitnessval;
	return max_id;
}

template <class T>
template<int n>
void MyGA<T>::GA(T (&x)[n], double& number) 
{
	create();
	bestchromo = &group[getBest(x, _bestval)];
	for (int i = 0; i < _n_generation; i++) 
	{
		select();//选择操作
		for(int j = 0; j < size; j++)
		{
			int p = rand() % len;
			int pre = len;
			int q = rand() % len;
			while(pre == p)
			{
				pre = rand() % len;
			}
			//根据概率交叉		
			if (rand0() < _pcross) 
			{
				cross(group[pre], group[p], q);
			}
		}
		for (int k = 0, pre = -1; k < _Size; k++) 
		{	//根据概率进行变异
			double d = rand0();
			if ((rand0() < _pmutate)) 
			{
				mutate(group[k]);
			}
		}
		getBest(x, number);
		cout << "第" << i+1 << "代" << "最优x值为:" << x[0]<<' '<< x[1]<<' '<< x[2]<<' '<< x[3]<<' '<< "函数值为" << _f(x) << endl;//结果的输出
	}
}
